HJ108 求最小公倍数

本节目标：理解“HJ108 求最小公倍数”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 描述 正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。 数据范围：

输入描述： 输入两个正整数A和B。 输出描述： 输出A和B的最小公倍数。 示例1 输入： 5 7 ==复制== 输出： 35 ==复制== 示例2 输入： 2 4 ==复制== 输出： 4

要计算两个正整数A和B的最小公倍数（LCM），一种有效的方法是先计算它们的最大公约数（GCD），然后使用这个公式：

这个公式的原理基于这样一个事实：两个数的乘积等于它们的最小公倍数和最大公约数的乘积。

def lcm(a, b): """计算最小公倍数（LCM）""" return a * b // gcd(a, b)

输入

a, b = map(int, input().split())

计算并输出最小公倍数

print(lcm(a, b))

这段代码首先定义了一个gcd函数，用于计算两个数的最大公约数，采用的是欧几里得算法。然后，lcm函数使用最大公约数来计算最小公倍数，并返回结果。最后，代码读取输入，调用lcm函数，并输出结果。

这个gcd函数是使用欧几里得算法（Euclidean algorithm）来计算两个正整数a和b的最大公约数（Greatest Common Divisor, GCD）。欧几里得算法是一种非常高效的算法，用于找出两个数的最大公约数，也就是能够同时整除它们的最大的数。